package junior.回溯法;

import sun.awt.SunHints;

public class 机器人收衣服 {
    static int[] stack = new int[10000];
    static int top = 1; // 栈指针（指向第二个元素，第一个元素固定为1，表示必有机器人）
    static int min_time = 1000000;
    static int Elec_Temp = 0; // 开放机器人的总电力
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n ,b ; // n: 衣服个数，栈的深度
//        n = scanner.nextInt();
//        b = scanner.nextInt();
//        int[][] Elec_time = new int[2][n];
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < n; j++) {
//                Elec_time[i][j] = scanner.nextInt();
//            }
//        }

        int n = 4, b = 6;  // 衣服个数、电力总数
        int[][] Elec_time = {{1,2,3,4},
                             {7,3,4,5}};

        initial(Elec_time);
        dfs(Elec_time,n,b);
        System.out.println("min_time = " + min_time);
    }

    public static void dfs(int[][] Elec_time,int n,int b){
        if(top == n){     // 重复取值的个数
            show(n,Elec_time);
            min_time = min_time(n,Elec_time) < min_time ? min_time(n,Elec_time) : min_time;
            return;
        }
        // 剪枝
        for (int i = 0; i <= 1; i++) {
            if(i == 0 || (Elec_Temp + Elec_time[0][top]) <= b){ // 逻辑修改
                stack[top++] = i;
                if(i == 1){
                    Elec_Temp += Elec_time[0][top-1];
                    dfs(Elec_time,n,b);
                    Elec_Temp -= Elec_time[0][--top];
                }else {
                    dfs(Elec_time,n,b);
                    top--;
                }
            } else
                return;
        }
    }
    public static int min_time(int n,int[][] Elec_time){
        int max_time = 0,pre_index = n;
        for (int i = n-1; i >=0; i--) {
            if(stack[i] == 1){
                max_time = Elec_time[1][i] * (pre_index-i) > max_time ? Elec_time[1][i] * (pre_index-i) : max_time;
                pre_index = i;
            }
        }
        return max_time;
    }
    public static void initial(int[][] Elec_time){
        stack[0] = 1;
        Elec_Temp = Elec_time[0][0];
    }
    public static void show(int n,int[][] Elec_time){
        for (int i = 0; i < top; i++) {
            System.out.print(stack[i]+"\t");
        }
        System.out.print("结果：" + min_time(n,Elec_time));
        System.out.println("\t Elec_Temp = " + Elec_Temp);
    }
}

